<!DOCTYPE html>
<html lang="zh-CN">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>算术表达式求值实验论文</title>
    <script src="https://cdn.jsdelivr.net/npm/mermaid@10/dist/mermaid.min.js"></script>
    <script>mermaid.initialize({ startOnLoad: true });</script>
    <style>
        body {
            font-family: '宋体', SimSun, serif;
            font-size: 12pt;
            /* 小四号字 */
            line-height: 1.5;
            margin: 2cm;
        }

        h1 {
            font-size: 16pt;
            /* 四号 */
            font-weight: bold;
            text-align: center;
        }

        h2 {
            font-size: 14pt;
            /* 小四号加粗 */
            font-weight: bold;
        }

        h3 {
            font-size: 12pt;
            /* 小四号加粗 */
            font-weight: bold;
        }

        p {
            text-indent: 2em;
            text-align: justify;
        }

        table {
            border-collapse: collapse;
            width: 100%;
            margin: 10px 0;
        }

        th,
        td {
            border: 1px solid #000;
            padding: 5px;
            text-align: center;
        }

        pre {
            font-family: 'Courier New', monospace;
            font-size: 10pt;
            margin: 10px 0;
            padding: 10px;
            border: 1px solid #ccc;
        }
    </style>
</head>

<body>
    <h1>算术表达式求值算法设计与实现</h1>

    <h2>1 引言与实验目标</h2>
    <p>在计算机科学领域，算术表达式的求值是一个基础且重要的问题，它不仅是计算器、程序编译器等系统软件的核心功能模块，也是数据结构课程中栈应用的经典案例。本次实验的核心目标是设计并实现能够处理包含多位整数、括号以及加、减、乘、除四则运算的算术表达式求值程序。通过该实验，我们旨在深入理解栈"后进先出"的特性，并探索如何运用该特性解决复杂的计算问题。为了更全面地探究该问题，我们并没有局限于单一的实现思路，而是并行设计了两种截然不同的算法方案：其一是借鉴了编译器中常用的算符优先法，通过构建优先级关系直接对中缀表达式进行计算；其二则采用了更为模块化的"中缀转后缀"策略，即将人类易于理解的中缀表达式转换为计算机易于处理的后缀表达式（逆波兰式），然后再进行求值。这两种方案在逻辑上各有侧重，为我们提供了一个绝佳的平台，以比较和分析不同算法在解决同一问题时的设计哲学与实现差异。
    </p>

    <h2>2 核心数据结构设计</h2>
    <p>为了有效支撑上述两种算法的实现，我们设计的核心数据结构是动态顺序栈。考虑到表达式求值过程中涉及两种不同类型的数据——数值（操作数）和符号（运算符），我们为这两种数据分别设计了专用的栈结构：即操作数栈（OPND）和运算符栈（OPTR）。这种职责分离的设计思路使得数据管理更为清晰。具体实现上，两个栈都采用了C语言中的结构体进行封装，内部包含一个指向栈底的基地址指针（base）、一个始终指向栈顶元素下一个位置的指针（top），以及一个记录当前栈容量的变量（stacksize）。为了应对表达式长度不确定的情况，我们为栈设计了动态扩容机制。当栈满时，程序能够自动申请更大的内存空间，并将原有数据迁移至新空间，从而确保了算法能够处理任意复杂度的表达式，避免了因固定容量限制而导致的程序崩溃，显著增强了程序的健壮性和普适性。
    </p>

    <div class="mermaid">
        graph TD
        subgraph "核心数据结构"
        OPND["SqStack_OPND<br />(操作数栈)"]
        OPTR["SqStack_OPTR<br />(运算符栈)"]
        end
        subgraph "栈结构定义"
        BASE["base: 栈底指针"]
        TOP["top: 栈顶指针"]
        SIZE["stacksize: 容量"]
        end
        OPND --> BASE
        OPND --> TOP
        OPND --> SIZE
        OPTR --> BASE
        OPTR --> TOP
        OPTR --> SIZE
    </div>

    <h2>3 核心算法设计与实现过程</h2>

    <h3>3.1 方案一：算符优先法的详细实现过程</h3>
    <p>在开始编写算符优先法的代码时，我首先面临的挑战是如何处理多位数的识别问题。传统教材中的算法通常只考虑单位数的情况，但实际应用中必须能够处理任意位数的整数。经过深入思考，我设计了一个状态机式的解析逻辑：当程序扫描到第一个数字字符时，它不会立即将其作为完整的操作数处理，而是继续向后探查，直到遇到非数字字符为止。在这个过程中，程序通过num
        = num * 10 + (exp[i] -
        '0')的方式逐位构建完整的多位数。这种实现方式不仅简洁高效，还能自然地处理任意位数的正整数。在实际编程过程中，我发现这个看似简单的逻辑实际上需要特别注意边界条件的处理，比如确保在读取完一个完整数字后，索引指针i的位置是正确的，不会跳过或重复处理字符。
    </p>

    <p>算符优先法的核心在于优先级表的构建和运用。我花费了相当多的时间来设计和验证这个7×7的优先级关系表。这个表不仅要涵盖基本的四则运算符（+、-、*、/），还要处理括号和表达式结束符#的优先级关系。在构建过程中，我逐一分析了每一对运算符相遇时的处理逻辑：例如，当栈顶是乘法运算符*而当前读入的是加法运算符+时，由于乘法优先级更高，应该立即执行乘法运算；而当栈顶是加法运算符+而当前读入的是乘法运算符*时，则应该将*压入栈中等待后续处理。最复杂的是括号的处理逻辑：左括号(与任何运算符相遇都应该被压栈，而右括号)的出现则触发栈内运算符的连续弹出，直到遇到匹配的左括号为止。在编程实现中，我使用了一个二维字符数组来存储这些优先级关系，并通过Precede函数来查询任意两个运算符之间的优先级关系。这种查表的方式虽然在空间上有一定开销，但极大地简化了运算逻辑的判断，使整个算法的可读性和可维护性都得到了显著提升。
    </p>

    <p>在具体的求值循环实现中，我采用了一个while循环来不断处理表达式中的每个字符，直到整个表达式处理完毕。循环的核心是一个复杂的条件判断结构：当遇到数字时调用多位数解析逻辑，当遇到运算符时则进入优先级比较和相应的处理分支。在优先级比较的结果处理上，我实现了三种不同的操作路径：当前运算符优先级较低时（返回'
        <'），直接将其压入运算符栈并继续读取下一个字符；当优先级相等时（返回'='），这通常意味着括号匹配，需要将栈顶的左括号弹出但不进行计算；当栈顶运算符优先级较高时（返回'>
            '），则需要立即执行计算操作。计算操作的实现相对直接：从运算符栈弹出一个运算符theta，从操作数栈弹出两个操作数a和b，然后调用Operate函数执行a theta
            b的运算，并将结果压回操作数栈。值得注意的是，由于栈的后进先出特性，弹出的两个操作数的顺序需要特别注意：后弹出的a是左操作数，先弹出的b是右操作数。这个细节在减法和除法运算中尤为重要，顺序错误会导致完全错误的计算结果。
    </p>

    <div class="mermaid">
        graph TD
        A[开始] --> B[初始化OPND和OPTR栈]
        B --> C[OPTR栈压入#]
        C --> D{扫描表达式字符}
        D --> E{字符类型判断}
        E -->|数字| F[多位数解析逻辑<br />读取完整数字并压入OPND]
        E -->|运算符| G[调用Precede函数<br />比较当前运算符与栈顶优先级]
        F --> D
        G --> H{优先级关系}
        H -->|小于| I[当前运算符压入OPTR<br />继续扫描下一字符]
        H -->|等于| J[弹出栈顶左括号<br />继续扫描下一字符]
        H -->|大于| K[弹出OPTR栈顶运算符<br />弹出OPND两个操作数<br />执行运算并压回结果]
        I --> D
        J --> D
        K --> G
        D --> L{表达式结束且栈顶为#?}
        L -->|否| E
        L -->|是| M[返回OPND栈顶结果]
        M --> N[结束]
    </div>

    <h3>3.2 方案二：中缀转后缀法的完整实现过程</h3>
    <p>中缀转后缀方案的实现让我对算法的模块化设计有了更深的理解。整个方案被我分解为两个相对独立的阶段：中缀表达式到后缀表达式的转换，以及后缀表达式的求值计算。这种分离式设计的好处在于，每个阶段都有明确的输入输出和单一的职责，使得调试和维护工作变得相对简单。在转换阶段的实现中，我同样需要处理多位数的识别问题，但与方案一不同的是，这里识别出的多位数需要直接输出到后缀表达式字符串中，而不是压入栈。为了在后缀表达式中正确分隔不同的操作数和运算符，我在每个数字和运算符后面都添加了一个空格字符作为分隔符。这个看似简单的细节实际上对后续的求值阶段至关重要，因为求值阶段需要能够准确地识别和解析后缀表达式中的每个元素。
    </p>

    <p>转换算法的核心逻辑体现在对不同类型字符的处理策略上。当遇到操作数时，算法直接将其追加到输出字符串中，这体现了后缀表达式"操作数优先输出"的特点。当遇到左括号时，算法将其无条件压入运算符栈，这是因为左括号在后缀表达式中不会出现，它的作用仅仅是标记一个子表达式的开始。当遇到右括号时，算法会触发一个连续的弹栈过程，将栈中的运算符依次弹出并追加到输出字符串，直到遇到匹配的左括号为止。这个过程巧妙地实现了括号内运算符的重新排序。最复杂的是普通运算符的处理：算法需要将栈中所有优先级大于等于当前运算符的栈顶运算符依次弹出并输出，然后才将当前运算符压入栈中。这个"大于等于"的判断条件是转换算法正确性的关键，它确保了后缀表达式中运算符的出现顺序严格遵循数学运算的优先级规则。在编程实现中，我使用了get_precedence函数来获取运算符的优先级数值，通过数值比较来判断优先级关系，这比方案一中的查表方式更加简洁直观。
    </p>

    <p>后缀表达式的求值阶段相对简单，但在实现细节上同样需要仔细考虑。求值算法使用一个操作数栈来存储计算过程中的中间结果。算法从左到右扫描后缀表达式，遇到操作数时将其压入栈中，遇到运算符时从栈中弹出两个操作数进行计算。这里同样需要注意操作数的顺序问题：由于栈的后进先出特性，先弹出的是右操作数，后弹出的是左操作数。在我的实现中，我使用了int
        a, b; Pop_OPND(&num_stack, &b); Pop_OPND(&num_stack,
        &a);的方式来确保操作数顺序的正确性。另一个需要特别处理的细节是后缀表达式中的空格分隔符：在扫描过程中，算法需要能够正确识别和跳过这些空格，同时准确解析多位数。我在实现中采用了状态机的方式来处理这个问题：当遇到数字字符时，算法进入数字解析状态，连续读取数字字符直到遇到空格或运算符为止；当遇到空格时，算法简单地跳过；当遇到运算符时，算法执行相应的计算操作。整个求值过程的最终结果就是操作数栈中剩余的唯一元素，这个设计体现了后缀表达式"无括号、无优先级"的优雅特性。
    </p>

    <h2>4 程序测试过程与结果分析</h2>

    <h3>4.1 测试用例设计与实现过程</h3>
    <p>为了全面验证两种算法的正确性和健壮性，我设计了一套系统性的测试方案。测试用例的设计遵循了从简单到复杂、从基础功能到边界情况的原则。首先，我设计了一系列基础的四则运算测试用例，包括简单的两数相加（如"12+34#"），多位数的混合运算（如"100-25*2#"），以及包含除法的计算（如"84/4+16#"）。这些基础测试的目的是验证算法对基本运算规则的正确处理，特别是运算符优先级的实现是否符合数学规则。在执行这些测试时，我发现了几个有趣的现象：方案一（算符优先法）在处理简单表达式时表现出了良好的直观性，整个计算过程与人工计算的思路高度一致；而方案二（中缀转后缀法）虽然需要两个阶段，但每个阶段的逻辑都非常清晰，特别是在观察中缀表达式如何转换为后缀表达式的过程中，能够直观地看到算法如何重新组织运算符的执行顺序。
    </p>

    <p>接下来，我设计了更加复杂的测试用例，主要涉及括号的使用和嵌套。括号测试是整个测试方案中最为关键的部分，因为括号的处理直接关系到表达式求值的正确性。我设计的测试用例包括简单的单层括号（如"(10+5)*3#"），复杂的多层嵌套括号（如"((10+20)*3+(40-15))/5#"），以及括号位置对计算结果影响的对比测试（如"10+20*3#"与"(10+20)*3#"的结果对比）。在执行这些测试的过程中，我深刻体会到了两种算法在处理括号时的不同策略。方案一通过优先级表中的等号关系来实现括号匹配，当遇到右括号时会连续执行栈内的运算直到遇到左括号，这种处理方式直接模拟了数学运算中括号的"强制优先"特性。方案二则将括号处理转化为栈操作：左括号作为"边界标记"压入栈中，右括号触发边界内运算符的输出，这种处理方式更加机械化但也更加可靠。通过对比测试，我发现两种方案在处理复杂括号表达式时都能得到正确的结果，但方案二的中间过程（后缀表达式）为调试提供了额外的信息，当出现错误时更容易定位问题所在。
    </p>

    <h3>4.2 详细测试结果与性能分析</h3>
    <p>经过系统性的测试，我收集了大量的测试数据，并对两种方案的性能进行了详细的分析。从正确性角度来看，两种方案在所有预设的测试用例中都获得了完全正确的结果，这验证了算法实现的可靠性。但在执行效率方面，两种方案展现出了不同的特性。方案一（算符优先法）的执行时间相对稳定，因为它只需要对表达式进行一次扫描，每个字符的处理时间基本恒定。但是，方案一需要频繁地查询优先级表和执行栈操作，在处理复杂表达式时可能会产生较多的中间计算。方案二（中缀转后缀法）虽然需要对表达式进行两次处理，但每次处理的逻辑都相对简单，特别是后缀表达式的求值阶段，由于没有优先级判断的开销，执行效率实际上非常高。
    </p>

    <table>
        <tr>
            <th>测试编号</th>
            <th>输入表达式</th>
            <th>算符优先法结果</th>
            <th>中缀转后缀法</th>
            <th>后缀表达式</th>
            <th>求值结果</th>
            <th>预期结果</th>
            <th>测试结论</th>
        </tr>
        <tr>
            <td>1</td>
            <td>12+34#</td>
            <td>46</td>
            <td>转换正常</td>
            <td>12 34 +</td>
            <td>46</td>
            <td>46</td>
            <td>通过</td>
        </tr>
        <tr>
            <td>2</td>
            <td>100-25*2#</td>
            <td>50</td>
            <td>转换正常</td>
            <td>100 25 2 * -</td>
            <td>50</td>
            <td>50</td>
            <td>通过</td>
        </tr>
        <tr>
            <td>3</td>
            <td>7+(30+8)*5#</td>
            <td>197</td>
            <td>转换正常</td>
            <td>7 30 8 + 5 * +</td>
            <td>197</td>
            <td>197</td>
            <td>通过</td>
        </tr>
        <tr>
            <td>4</td>
            <td>12+(100-20)/4*2#</td>
            <td>52</td>
            <td>转换正常</td>
            <td>12 100 20 - 4 / 2 * +</td>
            <td>52</td>
            <td>52</td>
            <td>通过</td>
        </tr>
        <tr>
            <td>5</td>
            <td>((10+20)*3+(40-15))/5#</td>
            <td>23</td>
            <td>转换正常</td>
            <td>10 20 + 3 * 40 15 - + 5 /</td>
            <td>23</td>
            <td>23</td>
            <td>通过</td>
        </tr>
        <tr>
            <td>6</td>
            <td>200*3-150/5+80#</td>
            <td>650</td>
            <td>转换正常</td>
            <td>200 3 * 150 5 / - 80 +</td>
            <td>650</td>
            <td>650</td>
            <td>通过</td>
        </tr>
    </table>

    <p>在深入分析测试结果的过程中，我发现了一些值得探讨的现象。首先，从调试友好性的角度来看，方案二展现出了明显的优势。当测试用例出现错误时，我可以通过观察生成的后缀表达式来快速定位问题所在。例如，在测试复杂括号嵌套时，我曾经遇到过一个括号匹配错误的情况，通过观察后缀表达式中运算符的顺序，我很快就发现了问题的根源。相比之下，方案一的调试过程更加依赖于对算法执行流程的理解，需要仔细跟踪栈的变化过程才能定位错误。其次，从算法的扩展性角度来看，两种方案也表现出了不同的特点。如果需要添加新的运算符（比如幂运算^或取模运算%），方案一需要扩展优先级表并相应修改比较逻辑，而方案二只需要在转换阶段增加新运算符的优先级判断即可，求值阶段的逻辑基本不需要修改。这种差异反映了两种算法设计思路的根本不同：方案一是一个整体性的解决方案，各个组件之间联系紧密；方案二是一个模块化的解决方案，各个阶段相对独立。
    </p>

    <p>通过对大量测试数据的统计分析，我还发现了两种算法在处理不同类型表达式时的性能差异。对于简单的线性表达式（如"a+b*c-d/e"），方案一的执行效率略高，因为它避免了中间字符串的生成和二次解析开销。但对于包含复杂括号嵌套的表达式，方案二的优势开始显现，因为后缀表达式的求值过程不需要考虑优先级问题，执行过程更加流畅。在内存使用方面，方案一主要的开销来自于两个栈的维护，而方案二除了栈的开销外，还需要存储中间生成的后缀表达式字符串。但考虑到现代计算机的内存容量，这种差异在实际应用中并不显著。更重要的是，通过这次详细的测试和分析过程，我对算法设计中的权衡艺术有了更深的理解：没有绝对完美的算法，只有在特定应用场景下更合适的解决方案。选择算法时需要综合考虑正确性、效率、可维护性、可扩展性等多个维度，这正是软件工程实践中最具挑战性和最有价值的部分。
    </p>

    <h2>5 讨论与展望</h2>
    <p>在成功实现基本功能之后，我们对当前程序存在的局限性及未来的改进方向进行了深入的思考。一个显而易见的问题是，当前两种方案都仅支持整数运算，这导致在进行除法运算时会丢失小数部分的精度。为了使程序更具实用性，一个重要的改进方向是引入浮点数支持。这需要将操作数栈的数据类型从int调整为double或float，并重写数字解析逻辑，使其能够正确识别和转换带有小数点的字符串。另一个值得探讨的方面是程序的错误处理机制。目前的实现主要针对合法的表达式输入，对于括号不匹配、运算符连续、非法字符等异常情况缺乏有效的检测和提示。在未来的版本中，可以引入一个独立的语法分析模块，在进行实际计算前对输入表达式的合法性进行预检查，并向用户返回明确的错误信息，这将极大地提升程序的用户体验和健壮性。
    </p>

    <h2>6 总结</h2>
    <p>通过本次算术表达式求值的实验，我们不仅巩固了对栈这一核心数据结构的理解，更在实践中锻炼了分析问题、设计算法和编写代码的综合能力。通过亲手实现算符优先法和中缀转后缀法这两种截然不同的技术路径，我们对算法设计的思想和权衡有了更为深刻的体悟。算符优先法以其直接、高效的方式模拟了人类的计算直觉，而中缀转后缀法则以其模块化、条理清晰的特点展现了工程化的解题思路。在整个开发过程中，从数据结构的设计、多位数的解析，到复杂逻辑的调试，每一步都充满了挑战，也带来了收获。我们认识到，一个看似简单的功能背后，往往需要严谨的逻辑设计和对各种边界情况的周全考虑。这次实验不仅是一次成功的编程实践，更是一次宝贵的思维训练，它让我们学会了如何将抽象的理论知识应用到具体的工程问题中，并为我们后续学习更为复杂的编译原理等课程打下了坚实的基础。
    </p>
</body>

</html>